The present invention is directed to optical matrix multiplication, and more particularly, to the high speed matrix multiplication of three matrices.
The multiplication of three matrices is often encountered in problems involving the computation of singular values of matrices or involving orthogonal transformation of matrices. In this regard, see the reference by H. C. Andrews and C. L. Patterson, IEEE Trans. on Acoustics, Speech Signal Processing, Vol., ASSP 24, p. 26 (1976); W. K. Pratt, "Digital Image Processing," (John Wiley Publ.) 1978. For example, the computation of singular values of a co efficient matrix would be used to solve the least squares problem. Additionally, triple matrix processing could be used in image processing and transmission. For example, an orthogonal transformation, separable in row and column spaces applied to imagery (e.g., Fourier Transform) could be obtained by means of a triple matrix product. Also, the triple matrix product could be used in order to obtain bandwidth compression of high resolution images. Additionally. triple matrix multiplication could be used in the computation of orthogonal moments of an image for pattern recognition.
The triple matrix product operation is defined as ##EQU1## where G is the input matrix which is left - and right -multiplied by the matrices U and V, respectively, producing the transformed matrix a. All of these matrices may be N.times.N square matrices for convenience. However, in the general case, each of the matrices have different dimensions, with the only requirement being that adJacent indices (the inner indices) for the matrices being multiplied be the same. This concept is illustrated as follows for the matrices U, G, and V: ##EQU2## It can be seen from the above that the inner matrix indices M for the matrices U and G match up, while the adjacent indices N for the matrices G and V also match up.
To illustrate a matrix of the type discussed, the G matrix containing M.times.N elements is represented below: ##EQU3## Similar representations are used for the matrices U and V.
A digital computer could be utilized in order to perform the above described triple matrix multiplication. However, the conventional serial digital processors require significant periods of time in order to effect such multiplications, particularly, for large matrices with dimensions on the order of 1000.times.1000. Optical techniques have been investigated for the purpose of matrix multiplication, since optics has the ability to perform many operations in parallel and thus would effect much faster matrix multiplication. In this regard, several optical processors have been developed for multiplying two matrices. See the article by R. A. Athale, "Optical Matrix Algebraic Processors: A Survey," Proceedings of the Tenth International Optical Computing Conference (1983), p. 24 (IEEE Cat. No. 83 Ch. 1880-4).
The triple matrix product operation typically is performed by first multiplying one matrix by a second matrix to obtain an intermediate result matrix, and then multiplying this intermediate result matrix by a third matrix. Although simple in principle, one of the main drawbacks of these two sequential multiplications, for either the digital or the optical approach, is that the intermediate result matrix produced by the first multiplication, e.g., U.multidot.G or G.multidot.V, must be stored and retrieved in the correct fashion. Thus, the required input-output interfacing between the two multiplication stages significantly slows the triple-matrix-product operation. For optical processors, additional input-output interfaces often reduce the dynamic range performance of the processors. Moreover, the sequential approach using the same two-matrix multiplier for both stages must always produce the full matrix answer since the intermediate result must be fully calculated. However, for a large number of practical applications only a few elements of the triple matrix product are needed. For example, in some applications only the diagonal elements, or the elements of a single row or a single column are required in order to obtain meaningful information. Accordingly, it is desirable, especially for optical processors with limited dynamic range, to apply their available optical power to the few matrix elements required, rather than generating the entire matrix.